home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / c-runtime / dispatch / RCS / hash.c,v < prev    next >
Encoding:
Text File  |  1992-08-18  |  30.0 KB  |  1,121 lines
  1. head    0.13;
  2. access;
  3. symbols;
  4. locks; strict;
  5. comment    @ * @;
  6.  
  7.  
  8. 0.13
  9. date    92.08.18.04.46.58;    author dglattin;    state Exp;
  10. branches;
  11. next    0.12;
  12.  
  13. 0.12
  14. date    92.04.13.11.43.08;    author dennisg;    state Exp;
  15. branches;
  16. next    0.11;
  17.  
  18. 0.11
  19. date    92.01.03.02.55.03;    author dennisg;    state Exp;
  20. branches;
  21. next    0.10;
  22.  
  23. 0.10
  24. date    91.12.10.12.05.28;    author dennisg;    state Exp;
  25. branches;
  26. next    0.9;
  27.  
  28. 0.9
  29. date    91.12.03.02.01.23;    author dennisg;    state Exp;
  30. branches;
  31. next    0.8;
  32.  
  33. 0.8
  34. date    91.11.24.01.20.02;    author dennisg;    state Exp;
  35. branches;
  36. next    0.7;
  37.  
  38. 0.7
  39. date    91.11.23.22.18.29;    author dennisg;    state Exp;
  40. branches;
  41. next    0.6;
  42.  
  43. 0.6
  44. date    91.11.21.22.27.06;    author dennisg;    state Exp;
  45. branches;
  46. next    0.5;
  47.  
  48. 0.5
  49. date    91.11.20.23.29.20;    author dennisg;    state Exp;
  50. branches;
  51. next    0.4;
  52.  
  53. 0.4
  54. date    91.11.19.12.34.41;    author dennisg;    state Exp;
  55. branches;
  56. next    0.3;
  57.  
  58. 0.3
  59. date    91.11.07.23.23.40;    author dennisg;    state Exp;
  60. branches;
  61. next    0.2;
  62.  
  63. 0.2
  64. date    91.11.07.22.30.54;    author dennisg;    state Exp;
  65. branches;
  66. next    0.1;
  67.  
  68. 0.1
  69. date    91.10.24.00.45.39;    author dennisg;    state Exp;
  70. branches;
  71. next    ;
  72.  
  73.  
  74. desc
  75. @This file contains the implementation of the hash table routines.
  76. @
  77.  
  78.  
  79. 0.13
  80. log
  81. @Saving a working version before release.
  82. @
  83. text
  84. @/* -*-c-*- */
  85.  
  86. /* Copyright (C) 1989, 1992 Free Software Foundation, Inc.
  87.  
  88. This file is part of GNU CC.
  89.  
  90. GNU CC is free software; you can redistribute it and/or modify
  91. it under the terms of the GNU General Public License as published by
  92. the Free Software Foundation; either version 2, or (at your option)
  93. any later version.
  94.  
  95. GNU CC is distributed in the hope that it will be useful,
  96. but WITHOUT ANY WARRANTY; without even the implied warranty of
  97. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  98. GNU General Public License for more details.
  99.  
  100. You should have received a copy of the GNU General Public License
  101. along with GNU CC; see the file COPYING.  If not, write to
  102. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  103.  
  104. /* As a special exception, if you link this library with files
  105.    compiled with GCC to produce an executable, this does not cause
  106.    the resulting executable to be covered by the GNU General Public License.
  107.    This exception does not however invalidate any other reasons why
  108.    the executable file might be covered by the GNU General Public License.  */
  109.  
  110. /* 
  111.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/dispatch.common/RCS/hash.c,v 0.12 1992/04/13 11:43:08 dennisg Exp dennisg $
  112.   $Author: dennisg $
  113.   $Date: 1992/04/13 11:43:08 $
  114.   $Log: hash.c,v $
  115.  * Revision 0.12  1992/04/13  11:43:08  dennisg
  116.  * Check in after array version of run-time works.
  117.  * Expect more changes as hash version and other changes are made.
  118.  *
  119.  * Revision 0.11  1992/01/03  02:55:03  dennisg
  120.  * modified to handle new initialization scheme.
  121.  * fixed code structure.
  122.  *
  123.  * Revision 0.10  1991/12/10  12:05:28  dennisg
  124.  * Cleaned up file format for a distribution.
  125.  *
  126.  * Revision 0.9  1991/12/03  02:01:23  dennisg
  127.  * fixed assert macro.
  128.  * added memory allocation adjustment macro for hash size allocation.
  129.  *
  130.  * Revision 0.8  1991/11/24  01:20:02  dennisg
  131.  * changed shorts back to ints.
  132.  * the efficiency gained didn't out weight the grossness of the code.
  133.  *
  134.  * Revision 0.7  1991/11/23  22:18:29  dennisg
  135.  * deleted hashIndex() and moved it to hash-inline.h
  136.  * converted hash_value_for_key () to a inline and moved it to hash-inline.h.
  137.  *
  138.  * Revision 0.6  1991/11/21  22:27:06  dennisg
  139.  * changed hash value calculation.
  140.  * func name changed from hashValue () to hashIndex().  the
  141.  * func really calculated a index anyway.
  142.  * changed hash func impl.  essentially it was calculating a hash value
  143.  * from a hash value.  this is a implementation thing.
  144.  *
  145.  * Revision 0.5  1991/11/20  23:29:20  dennisg
  146.  * converted hashIndex() to a inline.
  147.  *
  148.  * Revision 0.4  1991/11/19  12:34:41  dennisg
  149.  * bug in hash_delete ().  It was using void* to obtain nodes to
  150.  * pass to hash_remove ().  The value passed to hash_removed () is a
  151.  * entry from the node structure rather than the node itself.  Using
  152.  * void* removed compiler checking.
  153.  * Modified to implement cache expansion.
  154.  *
  155.  * Revision 0.3  1991/11/07  23:23:40  dennisg
  156.  * implemented hash table expansion as suggested by rms.
  157.  *
  158.  * Revision 0.2  1991/11/07  22:30:54  dennisg
  159.  * added copyleft
  160.  *
  161.  * Revision 0.1  1991/10/24  00:45:39  dennisg
  162.  * Initial check in.  Preliminary development stage.
  163.  *
  164. */
  165.  
  166.  
  167. #include  <hash.h>
  168. #include  <objc.h>
  169. #include  <objcP.h>
  170. #include  <objc-protoP.h>
  171.  
  172. #include  <assert.h>
  173. #include  <math.h>
  174. #include  <stdio.h>
  175. #include  <stdlib.h>
  176.  
  177.  
  178.                                                 /* These two macros determine
  179.                                                   when a hash table is full and
  180.                                                   by how much it should be 
  181.                                                   expanded respectively.
  182.                                                   
  183.                                                   These equations are 
  184.                                                   percentages. */
  185. #define FULLNESS(cache) \
  186.    ((((cache)->sizeOfHash * 75  ) / 100) <= (cache)->entriesInHash)
  187. #define EXPANSION(cache) \
  188.   ((cache)->sizeOfHash * 2 )
  189.  
  190. Cache_t 
  191. hash_new (u_int sizeOfHash, HashFunc aHashFunc, CompareFunc aCompareFunc) {
  192.  
  193.   Cache_t retCache;
  194.   
  195.  
  196.                                                                                                 /* Pass me a value greater
  197.                                                                                                     than 0 and a power of 2. */
  198.   assert(sizeOfHash);
  199.     assert( !(sizeOfHash & (sizeOfHash - 1)));
  200.   
  201.                                                 /* Allocate the cache 
  202.                                                   structure.  calloc () insures
  203.                                                   its initialization for
  204.                                                   default values. */
  205.   retCache = calloc (1, sizeof (Cache));
  206.   assert(retCache);
  207.   
  208.                                                 /* Allocate the array of 
  209.                                                   buckets for the cache.  
  210.                                                   calloc() initializes all of 
  211.                                                   the pointers to NULL. */
  212.   retCache->theNodeTable = calloc (sizeOfHash, sizeof (CacheNode_t));
  213.   assert(retCache->theNodeTable);
  214.   
  215.   retCache->sizeOfHash  = sizeOfHash;
  216.  
  217.                                                                                                 /* This should work for all
  218.                                                                                                     processor architectures? */
  219.     retCache->mask = ( sizeOfHash - 1 );
  220.     
  221.                                                                                                 /* Store the hashing function
  222.                                                                                                     so that codes can be 
  223.                                                                                                     computed. */
  224.     retCache->hashFunc = aHashFunc;
  225.  
  226.                                                                                                 /* Store the function that
  227.                                                                                                     compares hash keys to 
  228.                                                                                                     determine if they are 
  229.                                                                                                     equal. */
  230.     retCache->compareFunc = aCompareFunc;
  231.  
  232.   return retCache;
  233. }
  234.  
  235.  
  236. void 
  237. hash_delete (Cache_t theCache) {
  238.  
  239.   CacheNode_t aNode;
  240.   
  241.  
  242.                                                /* Purge all key/value pairs 
  243.                                                   from the table. */
  244.   while (aNode = hash_next (theCache, NULL))
  245.     hash_remove (theCache, aNode->theKey);
  246.  
  247.                                                 /* Release the array of nodes 
  248.                                                   and the cache itself. */
  249.   free (theCache->theNodeTable);
  250.   free (theCache);
  251. }
  252.  
  253.  
  254. void 
  255. hash_add (Cache_t* theCache, void* aKey, void* aValue) {
  256.  
  257.   u_int       indx = (* (*theCache)->hashFunc)(*theCache, aKey);
  258.   CacheNode_t aCacheNode = calloc (1, sizeof (CacheNode));
  259.  
  260.  
  261.   assert(aCacheNode);
  262.   
  263.                                                 /* Initialize the new node. */
  264.   aCacheNode->theKey    = aKey;
  265.   aCacheNode->theValue  = aValue;
  266.   aCacheNode->nextNode  = (* (*theCache)->theNodeTable)[ indx ];
  267.   
  268.                                                 /* Debugging.
  269.                                                 
  270.                                                   Check the list for another 
  271.                                                   key. */
  272. #ifdef DEBUG
  273.     { CacheNode_t checkHashNode = (* (*theCache)->theNodeTable)[ indx ];
  274.     
  275.       while (checkHashNode) {
  276.     
  277.         assert(checkHashNode->theKey != aKey);
  278.         checkHashNode = checkHashNode->nextNode;
  279.       }
  280.     }
  281. #endif
  282.  
  283.                                                 /* Install the node as the
  284.                                                   first element on the list. */
  285.   (* (*theCache)->theNodeTable)[ indx ] = aCacheNode;
  286.  
  287.                                                 /* Bump the number of entries
  288.                                                   in the cache. */
  289.   ++ (*theCache)->entriesInHash;
  290.   
  291.                                                 /* Check the hash table's
  292.                                                   fullness.   We're going
  293.                                                   to expand if it is above
  294.                                                   the fullness level. */
  295.   if (FULLNESS (*theCache)) {
  296.                                                 /* The hash table has reached
  297.                                                   its fullness level.  Time to
  298.                                                   expand it. 
  299.                                                   
  300.                                                   I'm using a slow method 
  301.                                                   here but is built on other
  302.                                                   primitive functions thereby
  303.                                                   increasing its 
  304.                                                   correctness. */
  305.     CacheNode_t aNode = NULL;
  306.     Cache_t     newCache = hash_new (EXPANSION (*theCache), 
  307.                                                                          (*theCache)->hashFunc, 
  308.                                                                          (*theCache)->compareFunc);
  309.  
  310.     DEBUG_PRINTF (stderr, "Expanding cache %#x from %d to %d\n",
  311.       *theCache, (*theCache)->sizeOfHash, newCache->sizeOfHash);
  312.       
  313.                                                 /* Copy the nodes from the
  314.                                                   first hash table to the
  315.                                                   new one. */
  316.     while (aNode = hash_next (*theCache, aNode))
  317.       hash_add (&newCache, aNode->theKey, aNode->theValue);
  318.  
  319.                                                 /* Trash the old cache. */
  320.     hash_delete (*theCache);
  321.     
  322.                                                 /* Return a pointer to the new
  323.                                                   hash table. */
  324.     *theCache = newCache;
  325.   }
  326. }
  327.  
  328.  
  329. void 
  330. hash_remove (Cache_t theCache, void* aKey) {
  331.  
  332.   u_int       indx = (*theCache->hashFunc)(theCache, aKey);
  333.   CacheNode_t aCacheNode = (*theCache->theNodeTable)[ indx ];
  334.   
  335.   
  336.                                                 /* We assume there is an entry 
  337.                                                   in the table.  Error if it 
  338.                                                   is not. */
  339.   assert(aCacheNode);
  340.   
  341.                                                 /* Special case.  First element 
  342.                                                   is the key/value pair to be 
  343.                                                   removed. */
  344.   if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) {
  345.     (*theCache->theNodeTable)[ indx ] = aCacheNode->nextNode;
  346.     free (aCacheNode);
  347.   } else {
  348.                                                 /* Otherwise, find the hash 
  349.                                                   entry. */
  350.     CacheNode_t prevHashNode = aCacheNode;
  351.     BOOL        removed = NO;
  352.     
  353.     do {
  354.     
  355.       if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) {
  356.         prevHashNode->nextNode = aCacheNode->nextNode, removed = YES;
  357.         free (aCacheNode);
  358.       } else
  359.         prevHashNode = aCacheNode, aCacheNode = aCacheNode->nextNode;
  360.     } while (!removed && aCacheNode);
  361.     assert(removed);
  362.   }
  363.   
  364.                                                 /* Decrement the number of
  365.                                                   entries in the hash table. */
  366.   --theCache->entriesInHash;
  367. }
  368.  
  369.  
  370. CacheNode_t 
  371. hash_next (Cache_t theCache, CacheNode_t aCacheNode) {
  372.  
  373.   CacheNode_t theCacheNode = aCacheNode;
  374.   
  375.   
  376.                                                 /* If the scan is being started
  377.                                                   then reset the last node 
  378.                                                   visitied pointer and bucket 
  379.                                                   index. */
  380.   if (!theCacheNode)
  381.     theCache->lastBucket  = 0;
  382.   
  383.                                                 /* If there is a node visited
  384.                                                   last then check for another 
  385.                                                   entry in the same bucket; 
  386.                                                   Otherwise step to the next 
  387.                                                   bucket. */
  388.   if (theCacheNode)
  389.     if (theCacheNode->nextNode)
  390.                                                 /* There is a node which 
  391.                                                   follows the last node 
  392.                                                   returned.  Step to that node 
  393.                                                   and retun it. */
  394.       return theCacheNode->nextNode;
  395.     else
  396.       ++theCache->lastBucket;
  397.  
  398.                                                 /* If the list isn't exhausted 
  399.                                                   then search the buckets for 
  400.                                                   other nodes. */
  401.   if (theCache->lastBucket < theCache->sizeOfHash) {
  402.                                                 /*  Scan the remainder of the 
  403.                                                   buckets looking for an entry
  404.                                                   at the head of the list.  
  405.                                                   Return the first item 
  406.                                                   found. */
  407.     while (theCache->lastBucket < theCache->sizeOfHash)
  408.       if ((*theCache->theNodeTable)[ theCache->lastBucket ])
  409.         return (*theCache->theNodeTable)[ theCache->lastBucket ];
  410.       else
  411.         ++theCache->lastBucket;
  412.   
  413.                                                 /* No further nodes were found
  414.                                                   in the hash table. */
  415.     return NULL;
  416.   } else
  417.     return NULL;
  418. }
  419.  
  420.  
  421.                                                 /* Given key, return its 
  422.                                                   value.  Return NULL if the
  423.                                                   key/value pair isn't in
  424.                                                   the hash. */
  425. void* 
  426. hash_value_for_key (Cache_t theCache, void* aKey) {
  427.  
  428.   CacheNode_t aCacheNode = 
  429.               (*theCache->theNodeTable)[(*theCache->hashFunc)(theCache, aKey)];
  430.   void*       retVal = NULL;
  431.   
  432.  
  433.   if (aCacheNode)
  434.     do {
  435.       if ((*theCache->compareFunc)(aCacheNode->theKey, aKey))
  436.         retVal = aCacheNode->theValue;
  437.       else
  438.         aCacheNode = aCacheNode->nextNode;
  439.     } while (!retVal && aCacheNode);
  440.   
  441.   return retVal;
  442. }
  443. @
  444.  
  445.  
  446. 0.12
  447. log
  448. @Check in after array version of run-time works.
  449. Expect more changes as hash version and other changes are made.
  450. @
  451. text
  452. @d1 28
  453. a28 19
  454. /* -*-c-*-
  455.  * This file contains the hashing implementation.
  456.  *
  457.  * Copyright (C) 1991 Threaded Technologies Inc.
  458.  * 
  459.  * This program is free software; you can redistribute it and/or modify
  460.  * it under the terms of the GNU General Public License as published
  461.  * by the Free Software Foundation; either version 1, or any later version.
  462.  * 
  463.  * This program is distributed in the hope that it will be useful,
  464.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  465.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  466.  * General Public License for more details.
  467.  * 
  468.  * You should receive a copy of the GNU General Public License 
  469.  * along with this program; if not, write to the Free Software
  470.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  471.  * 
  472.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/hash/RCS/hash.c,v 0.11 1992/01/03 02:55:03 dennisg Exp dennisg $
  473. d30 1
  474. a30 1
  475.   $Date: 1992/01/03 02:55:03 $
  476. d32 4
  477. @
  478.  
  479.  
  480. 0.11
  481. log
  482. @modified to handle new initialization scheme.
  483. fixed code structure.
  484. @
  485. text
  486. @d19 1
  487. a19 1
  488.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.10 1991/12/10 12:05:28 dennisg Exp dennisg $
  489. d21 1
  490. a21 1
  491.   $Date: 1991/12/10 12:05:28 $
  492. d23 4
  493. d72 3
  494. a74 3
  495. #include  <hash-inline.h>
  496. #include  <ObjC.h>
  497. #include  <ObjC-private.h>
  498. d92 1
  499. a92 1
  500.   (((cache)->sizeOfHash * 175 ) / 100 )
  501. d94 2
  502. a95 2
  503. #define MEMORY_ALLOCATION_ADJUST(i) \
  504.   ((i&0x01)?i:(i-1))
  505. a96 2
  506. Cache_t hash_new (u_int sizeOfHash) {
  507.  
  508. d100 2
  509. d103 1
  510. a104 6
  511.                                                 /* Memory is allocated on this
  512.                                                   machine in even address
  513.                                                   chunks.  Therefore the
  514.                                                   modulus must be odd. */
  515.   sizeOfHash = MEMORY_ALLOCATION_ADJUST(sizeOfHash);
  516.  
  517. d114 1
  518. a114 1
  519.                                                   calloc () initializes all of 
  520. d121 15
  521. d140 2
  522. a141 1
  523. void hash_delete (Cache_t theCache) {
  524. d146 1
  525. a146 1
  526.                                                 /* Purge all key/value pairs 
  527. d158 2
  528. a159 1
  529. void hash_add (Cache_t* theCache, void* aKey, void* aValue) {
  530. d161 1
  531. a161 1
  532.   u_int       indx = hashIndex(*theCache, aKey);
  533. d210 3
  534. a212 2
  535.     Cache_t     newCache = 
  536.                   hash_new (MEMORY_ALLOCATION_ADJUST( EXPANSION (*theCache)));
  537. d233 2
  538. a234 1
  539. void hash_remove (Cache_t theCache, void* aKey) {
  540. d236 1
  541. a236 1
  542.   u_int       indx = hashIndex(theCache, aKey);
  543. d248 1
  544. a248 1
  545.   if (aCacheNode->theKey == aKey) {
  546. d259 1
  547. a259 1
  548.       if (aCacheNode->theKey == aKey) {
  549. d274 2
  550. a275 1
  551. CacheNode_t hash_next (Cache_t theCache, CacheNode_t aCacheNode) {
  552. d325 22
  553. @
  554.  
  555.  
  556. 0.10
  557. log
  558. @Cleaned up file format for a distribution.
  559. @
  560. text
  561. @d19 1
  562. a19 1
  563.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.9 1991/12/03 02:01:23 dennisg Exp dennisg $
  564. d21 1
  565. a21 1
  566.   $Date: 1991/12/03 02:01:23 $
  567. d23 3
  568. a72 1
  569. #include  <libc.h>
  570. d74 3
  571. @
  572.  
  573.  
  574. 0.9
  575. log
  576. @fixed assert macro.
  577. added memory allocation adjustment macro for hash size allocation.
  578. @
  579. text
  580. @d19 1
  581. a19 1
  582.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.8 1991/11/24 01:20:02 dennisg Exp dennisg $
  583. d21 1
  584. a21 1
  585.   $Date: 1991/11/24 01:20:02 $
  586. d23 4
  587. d65 1
  588. a65 1
  589. #include    <hash-inline.h>
  590. d67 1
  591. a67 1
  592. #include    <ObjC-private.h>
  593. d73 11
  594. a83 11
  595.                                                                                                 /* These two macros determine
  596.                                                                                                     when a hash table is full and
  597.                                                                                                     by how much it should be 
  598.                                                                                                     expanded respectively.
  599.                                                                                                     
  600.                                                                                                     These equations are 
  601.                                                                                                     percentages. */
  602. #define    FULLNESS(cache)    \
  603.      ((((cache)->sizeOfHash * 75    ) / 100) <= (cache)->entriesInHash)
  604. #define    EXPANSION(cache) \
  605.     (((cache)->sizeOfHash * 175 ) / 100 )
  606. d85 2
  607. a86 2
  608. #define    MEMORY_ALLOCATION_ADJUST(i) \
  609.     ((i&0x01)?i:(i-1))
  610. d91 1
  611. a91 1
  612.     
  613. d94 6
  614. a99 6
  615.     
  616.                                                                                                 /* Memory is allocated on this
  617.                                                                                                     machine in even address
  618.                                                                                                     chunks.  Therefore the
  619.                                                                                                     modulus must be odd. */
  620.     sizeOfHash = MEMORY_ALLOCATION_ADJUST(sizeOfHash);
  621. d115 1
  622. a115 1
  623.   retCache->sizeOfHash    = sizeOfHash;
  624. d170 21
  625. a190 21
  626.                                                                                                 /* Bump the number of entries
  627.                                                                                                     in the cache. */
  628.     ++ (*theCache)->entriesInHash;
  629.     
  630.                                                                                                 /* Check the hash table's
  631.                                                                                                     fullness.   We're going
  632.                                                                                                     to expand if it is above
  633.                                                                                                     the fullness level. */
  634.     if (FULLNESS (*theCache)) {
  635.                                                                                                 /* The hash table has reached
  636.                                                                                                     its fullness level.  Time to
  637.                                                                                                     expand it. 
  638.                                                                                                     
  639.                                                                                                     I'm using a slow method 
  640.                                                                                                     here but is built on other
  641.                                                                                                     primitive functions thereby
  642.                                                                                                     increasing its 
  643.                                                                                                     correctness. */
  644.         CacheNode_t    aNode = NULL;
  645.         Cache_t            newCache = 
  646.                                     hash_new (MEMORY_ALLOCATION_ADJUST( EXPANSION (*theCache)));
  647. d192 8
  648. a199 8
  649.         DEBUG_PRINTF (stderr, "Expanding cache %#x from %d to %d\n",
  650.             *theCache, (*theCache)->sizeOfHash, newCache->sizeOfHash);
  651.             
  652.                                                                                                 /* Copy the nodes from the
  653.                                                                                                     first hash table to the
  654.                                                                                                     new one. */
  655.         while (aNode = hash_next (*theCache, aNode))
  656.             hash_add (&newCache, aNode->theKey, aNode->theValue);
  657. d201 7
  658. a207 7
  659.                                                                                                 /* Trash the old cache. */
  660.         hash_delete (*theCache);
  661.         
  662.                                                                                                 /* Return a pointer to the new
  663.                                                                                                     hash table. */
  664.         *theCache = newCache;
  665.     }
  666. d244 4
  667. a247 4
  668.     
  669.                                                                                                 /* Decrement the number of
  670.                                                                                                     entries in the hash table. */
  671.     --theCache->entriesInHash;
  672. @
  673.  
  674.  
  675. 0.8
  676. log
  677. @changed shorts back to ints.
  678. the efficiency gained didn't out weight the grossness of the code.
  679. @
  680. text
  681. @d19 1
  682. a19 1
  683.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.7 1991/11/23 22:18:29 dennisg Exp dennisg $
  684. d21 1
  685. a21 1
  686.   $Date: 1991/11/23 22:18:29 $
  687. d23 4
  688. d29 1
  689. a29 1
  690.  * converted hash_value_for_key() to a inline and moved it to hash-inline.h.
  691. d33 1
  692. a33 1
  693.  * func name changed from hashValue() to hashIndex().  the
  694. d42 2
  695. a43 2
  696.  * bug in hash_delete().  It was using void* to obtain nodes to
  697.  * pass to hash_remove().  The value passed to hash_removed() is a
  698. d77 1
  699. a77 1
  700.     ((((cache)->sizeOfHash * 75    ) / 100 ) <= (cache)->entriesInHash)
  701. d81 2
  702. d84 1
  703. a84 1
  704. Cache_t hash_new( u_int sizeOfHash ) {
  705. d87 1
  706. d89 7
  707. a96 2
  708.   assert( sizeOfHash );
  709.  
  710. d98 1
  711. a98 1
  712.                                                   structure.  calloc() insures
  713. d101 2
  714. a102 2
  715.   retCache = calloc( 1, sizeof( Cache ));
  716.   assert( retCache );
  717. d106 1
  718. a106 1
  719.                                                   calloc() initializes all of 
  720. d108 2
  721. a109 2
  722.   retCache->theNodeTable = calloc( sizeOfHash, sizeof( CacheNode_t ));
  723.   assert( retCache->theNodeTable );
  724. d111 1
  725. a111 1
  726.   retCache->sizeOfHash = sizeOfHash;
  727. d117 1
  728. a117 1
  729. void hash_delete( Cache_t theCache ) {
  730. d124 2
  731. a125 2
  732.   while( aNode = hash_next( theCache, NULL ))
  733.     hash_remove( theCache, aNode->theKey );
  734. d129 2
  735. a130 2
  736.   free( theCache->theNodeTable );
  737.   free( theCache );
  738. d134 1
  739. a134 1
  740. void hash_add( Cache_t* theCache, void* aKey, void* aValue ) {
  741. d136 2
  742. a137 2
  743.   u_int       indx = hashIndex( *theCache, aKey );
  744.   CacheNode_t aCacheNode = calloc( 1, sizeof( CacheNode ));
  745. d140 1
  746. a140 1
  747.   assert( aCacheNode );
  748. d145 1
  749. a145 1
  750.   aCacheNode->nextNode  = ( *( *theCache )->theNodeTable )[ indx ];
  751. d152 1
  752. a152 1
  753.     { CacheNode_t checkHashNode = ( *( *theCache )->theNodeTable )[ indx ];
  754. d154 1
  755. a154 1
  756.       while( checkHashNode ) {
  757. d156 1
  758. a156 1
  759.         assert( checkHashNode->theKey != aKey );
  760. d164 1
  761. a164 1
  762.   ( *( *theCache )->theNodeTable )[ indx ] = aCacheNode;
  763. d168 1
  764. a168 1
  765.     ++( *theCache )->entriesInHash;
  766. d174 1
  767. a174 1
  768.     if(FULLNESS( *theCache )) {
  769. a183 1
  770.         Cache_t            newCache = hash_new(EXPANSION( *theCache ));
  771. d185 2
  772. d189 1
  773. a189 1
  774.             *theCache, ( *theCache )->sizeOfHash, newCache->sizeOfHash);
  775. d194 2
  776. a195 2
  777.         while( aNode = hash_next( *theCache, aNode ))
  778.             hash_add( &newCache, aNode->theKey, aNode->theValue );
  779. d198 1
  780. a198 1
  781.         hash_delete( *theCache );
  782. d207 1
  783. a207 1
  784. void hash_remove( Cache_t theCache, void* aKey ) {
  785. d209 2
  786. a210 2
  787.   u_int       indx = hashIndex( theCache, aKey );
  788.   CacheNode_t aCacheNode = ( *theCache->theNodeTable )[ indx ];
  789. d216 1
  790. a216 1
  791.   assert( aCacheNode );
  792. d221 3
  793. a223 3
  794.   if( aCacheNode->theKey == aKey ) {
  795.     ( *theCache->theNodeTable )[ indx ] = aCacheNode->nextNode;
  796.     free( aCacheNode );
  797. d232 1
  798. a232 1
  799.       if( aCacheNode->theKey == aKey ) {
  800. d234 1
  801. a234 1
  802.         free( aCacheNode );
  803. d237 2
  804. a238 2
  805.     } while( !removed && aCacheNode );
  806.     assert( removed );
  807. d247 1
  808. a247 1
  809. CacheNode_t hash_next( Cache_t theCache, CacheNode_t aCacheNode ) {
  810. d256 1
  811. a256 1
  812.   if( !theCacheNode )
  813. d264 2
  814. a265 2
  815.   if( theCacheNode )
  816.     if( theCacheNode->nextNode )
  817. d277 1
  818. a277 1
  819.   if( theCache->lastBucket < theCache->sizeOfHash ) {
  820. d283 3
  821. a285 3
  822.     while( theCache->lastBucket < theCache->sizeOfHash )
  823.       if(( *theCache->theNodeTable )[ theCache->lastBucket ])
  824.         return ( *theCache->theNodeTable )[ theCache->lastBucket ];
  825. @
  826.  
  827.  
  828. 0.7
  829. log
  830. @deleted hashIndex() and moved it to hash-inline.h
  831. converted hash_value_for_key() to a inline and moved it to hash-inline.h.
  832. @
  833. text
  834. @d19 1
  835. a19 1
  836.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.6 1991/11/21 22:27:06 dennisg Exp dennisg $
  837. d21 1
  838. a21 1
  839.   $Date: 1991/11/21 22:27:06 $
  840. d23 4
  841. d124 1
  842. a124 1
  843.   u_short     indx = hashIndex( *theCache, aKey );
  844. d196 1
  845. a196 1
  846.   u_short     indx = hashIndex( theCache, aKey );
  847. @
  848.  
  849.  
  850. 0.6
  851. log
  852. @changed hash value calculation.
  853. func name changed from hashValue() to hashIndex().  the
  854. func really calculated a index anyway.
  855. changed hash func impl.  essentually it was calculating a hash value
  856. from a hash value.  this is a implementation thing.
  857. @
  858. text
  859. @d19 1
  860. a19 1
  861.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.5 1991/11/20 23:29:20 dennisg Exp dennisg $
  862. d21 1
  863. a21 1
  864.   $Date: 1991/11/20 23:29:20 $
  865. d23 7
  866. d53 1
  867. a73 9
  868. static inline u_int hashIndex( Cache_t theCache, void* aKey ) {
  869.  
  870.  
  871.     assert (sizeof (u_int) == sizeof (void*));
  872.     
  873.     return ((u_int)aKey) % theCache->sizeOfHash ;
  874. }
  875.  
  876.  
  877. d120 1
  878. a120 1
  879.   u_int       indx = hashIndex( *theCache, aKey );
  880. d192 1
  881. a192 1
  882.   u_int       indx = hashIndex( theCache, aKey );
  883. a226 22
  884. }
  885.  
  886.  
  887. void* hash_value_for_key( Cache_t theCache, void* aKey ) {
  888.  
  889.   u_int       indx = hashIndex( theCache, aKey );
  890.   CacheNode_t aCacheNode = ( *theCache->theNodeTable )[ indx ];
  891.   void*       retVal = NULL;
  892.   
  893.  
  894.   if( aCacheNode ) {
  895.     BOOL  found = NO;
  896.   
  897.     do {
  898.       if( aCacheNode->theKey == aKey )
  899.         retVal = aCacheNode->theValue, found = YES;
  900.       else
  901.         aCacheNode = aCacheNode->nextNode;
  902.     } while( !found && aCacheNode );
  903.   }
  904.   
  905.   return retVal;
  906. @
  907.  
  908.  
  909. 0.5
  910. log
  911. @converted hashValue() to a inline.
  912. @
  913. text
  914. @d19 1
  915. a19 1
  916.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.4 1991/11/19 12:34:41 dennisg Exp dennisg $
  917. d21 1
  918. a21 1
  919.   $Date: 1991/11/19 12:34:41 $
  920. d23 3
  921. d66 1
  922. a66 1
  923. static inline u_int hashValue( Cache_t theCache, void* aKey ) {
  924. a67 7
  925.   u_int hash = 0;
  926.   int   i;
  927.   
  928.   
  929.   assert( theCache->numberOfMaskBits );
  930.   for( i = 0; i < ( sizeof( aKey ) * 8 ); i += theCache->numberOfMaskBits )
  931.     hash ^= (( u_int )aKey ) >> i ;
  932. d69 3
  933. a71 1
  934.   return ( hash & theCache->mask ) % theCache->sizeOfHash;
  935. a77 1
  936.   int     i;
  937. a97 14
  938.                                                 /* Calculate the number of 
  939.                                                   bits required to represent 
  940.                                                   the hash mask. */
  941.   retCache->numberOfMaskBits = 
  942.     ceil( log( retCache->sizeOfHash ) / log( 2 ));
  943.  
  944.                                                 /* Form a bit mask for the 
  945.                                                   hash. */
  946.   for( i = 0; i < retCache->numberOfMaskBits; ++i )
  947.     retCache->mask = ( retCache->mask << 1 ) | 0x01 ;
  948.  
  949.   assert( retCache->numberOfMaskBits );
  950.   assert( retCache->mask );
  951.  
  952. d121 1
  953. a121 1
  954.   u_int       indx = hashValue( *theCache, aKey );
  955. d193 1
  956. a193 1
  957.   u_int       indx = hashValue( theCache, aKey );
  958. d233 1
  959. a233 1
  960.   u_int       indx = hashValue( theCache, aKey );
  961. @
  962.  
  963.  
  964. 0.4
  965. log
  966. @bug in hash_delete().  It was using void* to obtain nodes to
  967. pass to hash_remove().  The value passed to hash_removed() is a
  968. entry from the node structure rather than the node itself.  Using
  969. void* removed compiler checking.
  970. Modified to implement cache expansion.
  971. @
  972. text
  973. @d19 1
  974. a19 1
  975.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.3 1991/11/07 23:23:40 dennisg Exp dennisg $
  976. d21 1
  977. a21 1
  978.   $Date: 1991/11/07 23:23:40 $
  979. d23 7
  980. a61 2
  981.                                                 /* Local forward decl. */
  982.   u_int hashValue( Cache_t, void* );
  983. d63 1
  984. d65 12
  985. a318 13
  986.  
  987. u_int hashValue( Cache_t theCache, void* aKey ) {
  988.  
  989.   u_int hash = 0;
  990.   int   i;
  991.   
  992.   
  993.   assert( theCache->numberOfMaskBits );
  994.   for( i = 0; i < ( sizeof( aKey ) * 8 ); i += theCache->numberOfMaskBits )
  995.     hash ^= (( u_int )aKey ) >> i ;
  996.  
  997.   return ( hash & theCache->mask ) % theCache->sizeOfHash;
  998. }
  999. @
  1000.  
  1001.  
  1002. 0.3
  1003. log
  1004. @implemented hash table expansion as suggested by rms.
  1005. @
  1006. text
  1007. @d19 1
  1008. a19 1
  1009.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.2 1991/11/07 22:30:54 dennisg Exp dennisg $
  1010. d21 1
  1011. a21 1
  1012.   $Date: 1991/11/07 22:30:54 $
  1013. d23 3
  1014. d37 1
  1015. d50 4
  1016. a53 2
  1017. #define    FULLNESS        ( 100 / 75 )
  1018. #define    EXPANSION        ( 135 / 100 )
  1019. d103 1
  1020. a103 1
  1021.   void* aNode;
  1022. d109 1
  1023. a109 1
  1024.     hash_remove( theCache, aNode );
  1025. d129 1
  1026. a129 1
  1027.   aCacheNode->nextNode  = ( *( **theCache ).theNodeTable )[ indx ];
  1028. d136 1
  1029. a136 1
  1030.     { CacheNode_t checkHashNode = ( *( **theCache ).theNodeTable )[ indx ];
  1031. d148 1
  1032. a148 1
  1033.   ( *( **theCache ).theNodeTable )[ indx ] = aCacheNode;
  1034. d152 1
  1035. a152 1
  1036.     ++( **theCache ).entriesInHash;
  1037. d158 1
  1038. a158 1
  1039.     if(( **theCache ).entriesInHash * FULLNESS ) {
  1040. d168 1
  1041. a168 1
  1042.         Cache_t            newCache = hash_new(( **theCache ).sizeOfHash * EXPANSION );
  1043. d170 4
  1044. a173 1
  1045.         
  1046. @
  1047.  
  1048.  
  1049. 0.2
  1050. log
  1051. @added copyleft
  1052. @
  1053. text
  1054. @d19 1
  1055. a19 1
  1056.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.1 1991/10/24 00:45:39 dennisg Exp dennisg $
  1057. d21 1
  1058. a21 1
  1059.   $Date: 1991/10/24 00:45:39 $
  1060. d23 3
  1061. d39 9
  1062. d53 1
  1063. a53 1
  1064. Cache_t hash_new( u_int numberOfBuckets ) {
  1065. d59 1
  1066. a59 1
  1067.   assert( numberOfBuckets );
  1068. d72 1
  1069. a72 1
  1070.   retCache->theNodeTable = calloc( numberOfBuckets, sizeof( CacheNode_t ));
  1071. d75 1
  1072. a75 1
  1073.   retCache->numberOfBuckets = numberOfBuckets;
  1074. d81 1
  1075. a81 1
  1076.     ceil( log( retCache->numberOfBuckets ) / log( 2 ));
  1077. d112 1
  1078. a112 1
  1079. void hash_add( Cache_t theCache, void* aKey, void* aValue ) {
  1080. d114 1
  1081. a114 1
  1082.   u_int       indx = hashValue( theCache, aKey );
  1083. d123 1
  1084. a123 1
  1085.   aCacheNode->nextNode  = ( *theCache->theNodeTable )[ indx ];
  1086. d130 1
  1087. a130 1
  1088.     { CacheNode_t checkHashNode = ( *theCache->theNodeTable )[ indx ];
  1089. d138 1
  1090. d142 1
  1091. a142 1
  1092.   ( *theCache->theNodeTable )[ indx ] = aCacheNode;
  1093. d144 34
  1094. a177 1
  1095. #endif
  1096. d214 4
  1097. d273 1
  1098. a273 1
  1099.   if( theCache->lastBucket < theCache->numberOfBuckets ) {
  1100. d279 1
  1101. a279 1
  1102.     while( theCache->lastBucket < theCache->numberOfBuckets )
  1103. d303 1
  1104. a303 1
  1105.   return ( hash & theCache->mask ) % theCache->numberOfBuckets;
  1106. @
  1107.  
  1108.  
  1109. 0.1
  1110. log
  1111. @Initial check in.  Preliminary development stage.
  1112. @
  1113. text
  1114. @d4 22
  1115. a25 4
  1116.   $Header$
  1117.   $Author$
  1118.   $Date$
  1119.   $Log$
  1120. @
  1121.